class TreeNode:
    def __init__(self, x=0):
        self.val = x
        self.left = None
        self.right = None


def lowest_common_ancestor(root: TreeNode, o1: TreeNode, o2: TreeNode):
    """
    找o1, o2节点的最近公共祖先
    :param root:
    :param o1:
    :param o2:
    :return:
    """
    # 记录每个节点的父节点，根节点的父节点是自身
    dic = {root: root}

    def process(root: TreeNode):
        if not root:
            return
        if root.left:
            dic[root.left] = root
        if root.right:
            dic[root.right] = root
        process(root.left)
        process(root.right)

    process(root)
    # o1的所有父节点列表
    lst = []
    while dic[o1] != o1:
        lst.append(o1)
        o1 = dic[o1]
    # 找o2的父节点，如果在o1的父节点中，则返回
    while dic[o2] != o2:
        if o2 in lst:
            return o2
        o2 = dic[o2]
    return root


def lowest_common_ancestor1(root: TreeNode, o1: TreeNode, o2: TreeNode):
    if not root or root == o1 or root == o2:
        return root
    l = lowest_common_ancestor1(root.left, o1, o2)
    r = lowest_common_ancestor1(root.right, o1, o2)
    if l and r:
        return root

    return l if l else r


if __name__ == "__main__":
    head = TreeNode(6)
    head.left = TreeNode(3)
    head.left.left = TreeNode(1)
    head.left.left.right = TreeNode(2)
    head.left.right = TreeNode(4)
    head.left.right.right = TreeNode(5)
    head.right = TreeNode(9)
    head.right.left = TreeNode(8)
    head.right.left.left = TreeNode(7)
    head.right.right = TreeNode(10)

    res = is_banlance_tree(head)
    print(res.is_bt)
